<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Toom-Cook-Algorithmus</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Toom-Cook-Algorithmus"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Toom-Cook-Algorithmus rootpage-Toom-Cook-Algorithmus skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Toom-Cook-Algorithmus</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Toom-Cook-Algorithmus</b> ist ein <a href="Effizienz_(Informatik)" title="Effizienz (Informatik)">effizienter</a> <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur <a href="Multiplikation" title="Multiplikation">Multiplikation</a> zweier <a href="Ganze_Zahl" title="Ganze Zahl">ganzer Zahlen</a>, der nach dem Prinzip <i><a href="Teile_und_herrsche_(Informatik)" class="mw-redirect" title="Teile und herrsche (Informatik)">Teile und herrsche</a></i> arbeitet. Er wurde zuerst von Andrei Toom beschrieben, später durch <a href="Stephen_A._Cook" title="Stephen A. Cook">Cook</a> verbessert und in dessen Doktorarbeit veröffentlicht.
</p><p>Er existiert in zwei Varianten. Die Variante mit <i>fester Teilung</i> besitzt eine <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Laufzeitkomplexität</a> von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(n^{1+\varepsilon }\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mrow>
<mo>(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
<mo>+</mo>
<mi>ε<!-- ε --></mi>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O\left(n^{1+\varepsilon }\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfa7b8a8bd8b443d830b0ac3a21a07298361fd70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.784ex; height:3.343ex;" alt="{\displaystyle O\left(n^{1+\varepsilon }\right)}" loading="lazy"></span>, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ε<!-- ε --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> abhängt. Die Variante mit <i>variabler Teilung</i> besitzt Laufzeitkomplexität <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(n\cdot \log(n)\cdot 2^{\sqrt {2\log(n)}}\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mrow>
<mo>(</mo>
<mrow>
<mi>n</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>log</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>⋅<!-- ⋅ --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mn>2</mn>
<mi>log</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</msqrt>
</mrow>
</msup>
</mrow>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O\left(n\cdot \log(n)\cdot 2^{\sqrt {2\log(n)}}\right)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b84e7fec905eb0bf7f1c0cb4bf5cece3067f85e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:24.478ex; height:4.843ex;" alt="{\displaystyle O\left(n\cdot \log(n)\cdot 2^{\sqrt {2\log(n)}}\right)}" loading="lazy"></span>.
</p><p>Der Algorithmus ist die Verallgemeinerung des <a href="Karatsuba-Algorithmus" class="mw-redirect" title="Karatsuba-Algorithmus">Karatsuba-Algorithmus</a> und deutlich schneller als der naive Algorithmus nach der Schulmethode (bzw. der <a href="Russische_Bauernmultiplikation" title="Russische Bauernmultiplikation">russischen Bauernmultiplikation</a> im <a href="Dualsystem" title="Dualsystem">Binärsystem</a>), der Laufzeitkomplexität <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n^{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></span> besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der <a href="Sch%C3%B6nhage-Strassen-Algorithmus" title="Schönhage-Strassen-Algorithmus">Schönhage-Strassen-Algorithmus</a>, dessen Laufzeitkomplexität <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="1.623em" minsize="1.623em">(</mo>
</mrow>
</mrow>
<mi>n</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>log</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>⋅<!-- ⋅ --></mo>
<mi>log</mi>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="1.2em" minsize="1.2em">(</mo>
</mrow>
</mrow>
<mi>log</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="1.2em" minsize="1.2em">)</mo>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="1.623em" minsize="1.623em">)</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ea5547b9304acb80abd8162ce335945c7130438f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:27.529ex; height:4.843ex;" alt="{\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}" loading="lazy"></span> beträgt und der aus Sicht der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> als schnellster, praktisch angewandter, Algorithmus zur Multiplikation ganzer Zahlen gilt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><a rel="nofollow" class="external text" href="http://cr.yp.to/bib/1966/cook.html">Doktorarbeit von Stephen Cook</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2019-03-20" href="https://de.wikipedia.org/wiki/?title=Toom-Cook-Algorithmus&oldid=186778560">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>